{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 决策树C4.5算法\n",
    "\n",
    "上一节我们讲到ID3算法有四个主要的不足，一是不能处理连续特征，第二个就是用信息增益作为标准容易偏向于取值较多的特征，最后两个是缺失值处理的问和过拟合问题。\n",
    "\n",
    "昆兰在C4.5算法中改进了上述4个问题。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "对于第一个问题，不能处理连续特征， C4.5的思路是将连续的特征离散化。\n",
    "\n",
    "对于第二个问题，信息增益作为标准容易偏向于取值较多的特征的问题。\n",
    "\n",
    "我们引入一个信息增益比的变量$I_R(X,Y)IR(X,Y)$，它是信息增益和特征熵的比值。表达式如下："
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$I_R(D,A)=\\frac{I(A,D)}{H_A(D)}$$\n",
    "\n",
    "其中D为样本特征输出的集合，A为样本特征，对于特征熵$H_A(D)$, 表达式如下：\n",
    "\n",
    "$$H_A(D)=−∑_i^n\\frac{|D_i|}{|D|}log_2\\frac{|D_i|}{|D|}$$\n",
    "\n",
    "\n",
    "其中n为特征A的类别数， $|D_i|$为特征A取第i个值时对应的样本个数。|D|为总样本个数。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "对于第三个缺失值处理的问题，主要需要解决的是两个问题，\n",
    "\n",
    ">**一**是在样本某些特征缺失的情况下选择划分的属性\n",
    "\n",
    ">**二**是选定了划分属性，对于在该属性上缺失特征的样本的处理。\n",
    "\n",
    "对于第一个子问题，对于某一个有缺失特征值的特征A。C4.5的思路是将数据分成两部分，对每个样本设置一个权重（初始可以都为1），然后划分数据，一部分是有特征值A的数据D1，另一部分是没有特征A的数据D2. 然后对于没有缺失特征A的数据集D1来和对应的A特征的各个特征值一起计算加权重后的信息增益比，最后乘上一个系数，这个系数是无特征A缺失的样本加权后所占加权总样本的比例。\n",
    "\n",
    "对于第二个子问题，可以将缺失特征的样本同时划分入所有的子节点，不过将该样本的权重按各个子节点样本的数量比例来分配。\n",
    "\n",
    "比如缺失特征A的样本a之前权重为1，特征A有3个特征值A1,A2,A3。 3个特征值对应的无缺失A特征的样本个数为2,3,4.则a同时划分入A1，A2，A3。对应权重调节为2/9,3/9, 4/9。\n",
    "\n",
    "对于第4个问题，C4.5引入了正则化系数进行初步的剪枝。具体方法这里不讨论。下篇讲CART的时候会详细讨论剪枝的思路。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**不足**\n",
    "\n",
    "**1)**由于决策树算法非常容易过拟合，因此对于生成的决策树必须要进行剪枝。剪枝的算法有非常多，C4.5的剪枝方法有优化的空间。思路主要是两种\n",
    "\n",
    "一种是预剪枝，即在生成决策树的时候就决定是否剪枝。\n",
    "\n",
    "另一个是后剪枝，即先生成决策树，再通过交叉验证来剪枝。\n",
    "\n",
    "后面在下篇讲CART树的时候我们会专门讲决策树的减枝思路，主要采用的是后剪枝加上交叉验证选择最合适的决策树。\n",
    "\n",
    "**2)**C4.5生成的是多叉树，即一个父节点可以有多个节点。很多时候，在计算机中二叉树模型会比多叉树运算效率高。如果采用二叉树，可以提高效率。\n",
    "\n",
    "**3)**C4.5只能用于分类，如果能将决策树用于回归的话可以扩大它的使用范围。\n",
    "\n",
    "**4)**C4.5由于使用了熵模型，里面有大量的耗时的对数运算,如果是连续值还有大量的排序运算。如果能够加以模型简化可以减少运算强度但又不牺牲太多准确性的话，那就更好了。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
